/* A,B两个单链表递增有序，从A，B中找出公共元素产生单链表C，要求不破环A，B结点 */
#include <iostream>
#include "headfun.h"
using namespace std;

// 创建由公共元素组成的链表
Linklist common(LNode *A, LNode *B)
{
  // 两指针分别指向链表A、链表B
  LNode *p = A->next;
  LNode *q = B->next;
  
  // 初始化链表C
  LNode *C = new LNode;
  
  // 辅助指针
  LNode *r = C, *s;
  
  // 遍历两链表
  while (p != NULL && q != NULL)
  {
    // A结点更小，移动到A的下一个结点
    if (p->data < q->data)
      p = p->next;
    
    // B结点更小，移动到B的下一个结点
    else if (p->data > q->data)
      q = q->next;
    
    // 两结点数值相等
    else
    {
      // 创建新结点，添加进链表C
      s = new LNode;
      s->data = p->data;
      r->next = s;
      r = s;
      
      // 移动到下一个结点
      p = p->next;
      q = q->next;
    }
  }
  
  r->next = NULL;
  return C;
}

int main()
{
  // 创建两个递增链表
  cout << " 链表A:";
  LNode *A = head_Linklist();
  cout << " 链表B:";
  LNode *B = head_Linklist();
  
  // 公共元素组成的链表
  LNode *C = common(A, B);
  
  // 打印
  LNode *q = C->next;
  while (q != NULL)
  {
    cout << q->data << " ";
    q = q->next;
  }
  return 0;
}